package com.peng.leetcode.dfs;

import java.util.HashMap;
import java.util.Map;

/**
 * MaxAreaOfIsland
 * <p>
 * 695. 岛屿的最大面积
 *
 * @author: lupeng6
 * @create: 2021/1/22 21:22
 */
public class MaxAreaOfIsland {

    public static void main(String[] args) {
        int[][] grid = {{0, 1, 1}, {1, 1, 0}};
        System.out.println(new Solution().maxAreaOfIsland(grid));
    }

    /**
     * 岛屿的最大面积
     * 使用深度优先的方法求解
     *
     * @author lupeng6
     * @date 2021/1/22 21:23
     */
    static class Solution {

        private Map<Integer, Integer> union = new HashMap<>();

        private int rows;

        private int cols;

        private int[][] grid;

        private int[][] operations = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        private boolean[][] visited;

        public int maxAreaOfIsland(int[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            this.grid = grid;
            this.rows = grid.length;
            this.cols = grid[0].length;
            this.visited = new boolean[rows][cols];

            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (grid[i][j] == 1 && !visited[i][j]) {
                        int index = i * cols + j;
                        union.putIfAbsent(index, 0);
                        dfs(i, j, index);
                    }
                }
            }
            if (union.isEmpty()) {
                return 0;
            }
            return (int) union.values().stream().sorted((a, b) -> b - a).toArray()[0];
        }

        private void dfs(int x, int y, int index) {
            visited[x][y] = true;
            union.computeIfPresent(index, (key, val) -> val + 1);
            for (int[] operation : operations) {
                int newX = x + operation[0];
                int newY = y + operation[1];
                if (isArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == 1) {
                    dfs(newX, newY, index);
                }
            }
        }

        private boolean isArea(int x, int y) {
            return x >= 0 && x < rows && y >= 0 && y < cols;
        }
    }
}
